package com.cskaoyan.javase.recursion._1basic;

/**
 * 递归的思想:
 * 引例：使用递归计算N（N>=1）的阶乘（factorial）
 * n! = n * (n-1) * (n-1) * .. * 1
 * 这里实际上完全可以不用递归,可以用循环做,使用循环最主要的是,需要找到循环体语句
 *
 * 用递归求解n!
 * 递归指的是在方法当中调用方法自身,并且递归需要出口,这意味递归是把一个问题,
 *      变成一个更小规模的问题,用同样的方式去解决
 *      这种分解问题的思想就是递归的思想
 *      所以要想使用递归,就必须去考虑分解问题,往分解的方向上去靠,从而找到递归体和递归的出口
 * n! = n * (n-1)!
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 分解不是无限制进行的
 * 当n=1时,n! = 1
 * 所以递归体和递归的出口就找到了:
 * 假设n的阶乘是f(n)
 *  递归体: f(n)= n* f(n-1)
 *  递归的出口: f(1) = 1
 *
 *  以上递归的求解过程,总结递归的思想:
 *      1.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。
 *      2.当子问题规模足够小的时候，就可以直接得到小规模问题的解。
 *      3.然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * 递归的优点:
 *      1.递归求解的代码往往十分简洁,优雅
 *      2.递归的分解的思想,非常符合人类的思维
 *
 * 递归的缺点:
 *      1.递归很危险,容易栈溢出
 *      2.递归是分解问题求解的过程,在这个过程中需要频繁调用方法,频繁求解,往往存在大量重复计算的部分
 *      这导致递归求解
 *      不仅耗费内存,而且效率也很差
 *      时空复杂度都不优越
 *
 * @since 17:19
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoop(7));
        System.out.println(factorialRecursion(7));
    }

    // 用循环求解阶乘
    public static long factorialLoop(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    // 用递归求解阶乘
    public static long factorialRecursion(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        return n * factorialRecursion(n - 1);
    }

}
